#pragma once
#include<iostream>

using std::pair;
using std::cout;
using std::endl;

enum Color{RED=1,BLACK};

template<class T>
struct RBTreeNode
{
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;

    Color _col;

    RBTreeNode(const T& data)
    :_data(data)
    ,_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_col(RED)
    {}
};

template<class T>
struct __map_iterator
{
    typedef struct RBTreeNode<T> Node;
    typedef struct __map_iterator<T> self;
public:
    __map_iterator(Node* node):_node(node){}

    T& operator*()
    {
        return _node->_data;
    }

    T* operator->()
    {
        return &(_node->_data);//用于自定义类型的节点data，外界调用->本质上被编译器优化省略了一个->
    }

    self& operator++()
    {
        Node* cur=_node;//返回红黑树中序遍历的下一个结点
        //怎么找中序遍历的下一个结点？ --- 根据中序遍历的规则：左子树 根 右子树，cur目前处在根的位置，下一个要找右子树，可分两种情况讨论
        //1.cur的右子树存在，就找右子树的最左结点(最小结点)
        if(cur->_right)
        {
            Node* right_min=cur->_right;
            while(right_min->_left)
                right_min=right_min->_left;
            _node=right_min;
        }
        //2.右子树不存在，就向上寻找“自己是父节点左子树”的那棵“父子树”
        else 
        {
            Node* parent=cur->_parent;
            while(parent && cur==parent->_right)
                cur=parent,parent=parent->_parent;
            //跳出循环有两种情况 1.parent==nullptr   2.cur!=parent->_right  但无论哪种情况parent都是自己要找的目标对象！
            _node=parent;
        }
        return *this;//构造+隐式类型转换
    }

    bool operator!=(const self& goal)
    {
        return _node!=goal._node;//指针之间的比较，是内置类型的比较，无需为_node类型写重载
    }

private:
    Node* _node;
};


template<class K,class T,class KeyOfT>
class RBTree
{
    typedef struct RBTreeNode<T> Node;
public:
    typedef struct __map_iterator<T> iterator;

    iterator begin()
    {
        Node* most_left=_root;
        while(most_left->_left)
            most_left=most_left->_left;
        return iterator(most_left);
    }
    iterator end()
    {
        return iterator(nullptr);
    }

    RBTree():_root(nullptr){}

    bool Insert(const T& data)//T既可能是key  也可能是pair<K,V>  那pair怎么用key比较？？ ---仿函数
    {
        if(_root==nullptr)
        {
            _root=new Node(data),_root->_col=BLACK;
            return true;
        }

        //1.根据kv.first，找位置

        KeyOfT kot;//用来充当pair<K,V>拿到key的载体

        Node* cur=_root,*parent=nullptr;
        while(cur)
        {
            if(kot(data)>kot(cur->_data))
                parent=cur,cur=cur->_right;
            else if(kot(data)<kot(cur->_data))
                parent=cur,cur=cur->_left;
            else return false;//说明有key值相同的节点
        }
        //2.将newnode插入树中
        cur=new Node(data);
        if(kot(data)>kot(parent->_data))
            parent->_right=cur,cur->_parent=parent;
        else 
            parent->_left=cur,cur->_parent=parent;
        //3.更新结点颜色
        while(parent && parent->_col==RED)
        {
            Node* grandparent=parent->_parent;//此时，grandparent必定不为空，且为黑色
            //判断parent是grandparent的哪棵子树
            if(parent==grandparent->_left)
            {
                Node* uncle=grandparent->_right;
                //判断uncle的状态
                if(uncle && uncle->_col==RED)
                {
                    parent->_col=uncle->_col=BLACK;
                    grandparent->_col=RED;//变色

                    cur=grandparent,parent=cur->_parent;//继续向上更新
                }
                //uncle不存在，或存在且为黑，需要旋转+变色
                else if(cur==parent->_left)//判断cur是parent的哪棵子树
                {
                    RotateR(grandparent);//右单旋
                    parent->_col=BLACK,grandparent->_col=RED;//变色
                }
                else if(cur==parent->_right)
                {
                    RotateL(parent);//先左旋
                    RotateR(grandparent);//再右旋
                    cur->_col=BLACK,grandparent->_col=RED;//变色
                    break;
                } 
            }
            else 
            {
                Node* uncle=grandparent->_left;
                //判断uncle的状态
                if(uncle && uncle->_col==RED)
                {
                    parent->_col=uncle->_col=BLACK;
                    grandparent->_col=RED;//变色

                    cur=grandparent,parent=cur->_parent;//继续向上更新
                }
                else if(cur==parent->_right)
                {
                    RotateL(grandparent);//左单旋
                    parent->_col=BLACK,grandparent->_col=RED;//变色
                }
                else if(cur==parent->_left)
                {
                    RotateR(parent);//先右旋
                    RotateL(grandparent);//再左旋
                    cur->_col=BLACK,grandparent->_col=RED;//变色
                    break;
                }
            }
        }
        _root->_col=BLACK;
        return true;
    }   

    void InOrder()
    {
        KeyOfT kot;
        _InOrder(_root,kot);
        cout<<endl;
    }

    bool Is_Balance()
    {
        //1.根节点黑色   
        if(_root->_col!=BLACK)return false;

        //找个基准值
        int black_size=0;
        Node* cur=_root;
        while(cur)
        {
            if(cur->_col==BLACK)black_size++;
            cur=cur->_left;
        }

        //2.不能有连续的红色节点   3.每条支路黑色结点个数相等
        return _Is_Red_Row(_root,0,black_size);
    }

private:
    void RotateL(Node* parent)
    {
        Node* grandparent=parent->_parent;
        Node* cur=parent->_right;
        Node* curleft=cur->_left;

        parent->_right=curleft;
        parent->_parent=cur;

        if(curleft)
            curleft->_parent=parent;

        cur->_left=parent;
        cur->_parent=grandparent;

        if(grandparent==nullptr)
            _root=cur;
        else 
        {
            if(grandparent->_left==parent)
                grandparent->_left=cur;
            else 
                grandparent->_right=cur;
        }
    }

    void RotateR(Node* parent)
    {
        Node* grandparent=parent->_parent;

        Node* cur=parent->_left;
        Node* curright=cur->_right;

        parent->_left=curright;
        parent->_parent=cur;

        if(curright)
            curright->_parent=parent;
        
        cur->_right=parent;
        cur->_parent=grandparent;

        if(grandparent==nullptr)
            _root=cur;
        else 
        {
            if(parent==grandparent->_left)
                grandparent->_left=cur;
            else 
                grandparent->_right=cur;
        }
    }

    void _InOrder(Node* root,KeyOfT& kot)
    {
        if(root==nullptr)
            return;
        _InOrder(root->_left,kot);
        cout<<kot(root->_data)<<" ";
        _InOrder(root->_right,kot);
    }

    bool _Is_Red_Row(Node* root,int black_number,int standard)
    {
        if(root==nullptr)
        {
            if(black_number!=standard)return false;//判断每条树分支的黑色结点个数是否相等
            return true;
        }
        if(root->_col==BLACK)black_number++;//记录每条树分支的黑色结点个数
        if(root->_col==RED && root->_parent->_col==RED)//判断是否出现连续的红色节点
            return false;
        return _Is_Red_Row(root->_left,black_number,standard) && _Is_Red_Row(root->_right,black_number,standard);
    }

private:
    Node* _root;
};